package c;



/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-29
 * Time: 15:11
 */
public class TestHeap implements IList {
    public int[] elem ;
    public int usedSize;
    public TestHeap(int k){
        this.elem = new int[k];//初始容量
    }
     //堆的插入
     public void offer(int val){
        elem[usedSize] = val;
        usedSize++;
        //向上调整
         shiftUp(usedSize-1);
     }
     public void shiftUp(int child){
        int parent =(child -1) / 2;
        while(child > 0){
            if(elem[child] < elem[parent]){
                swap(child ,parent);
                child = parent;
                parent = (child -1 ) / 2;
            }else{
                break;
            }
        }

     }
     //堆的删除
     public int poll(){
        int tmp = elem[0];
        swap(0 ,usedSize-1);
        usedSize--;
        //向下调整
        shiftDown(0,usedSize);
        return tmp;
     }
     public int peek(){
        return elem[0];
     }
     private void shiftDown(int parent ,int len){
        int child = parent *2+1;
        while(child < len){
            if(child +1 < elem.length && elem[child] > elem[child+1]){
                child ++;
            }
            if(elem[parent] > elem[child]){
                swap(parent,child);
                parent =child ;
                child = 2* parent+1;
            }else {
                break;
            }
        }
     }
     private void swap(int i,int j){
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
     }


}
